package com.zwxu.list;

public class InsertionSortListDemo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(3);
		ListNode node3 = new ListNode(5);
		ListNode node4 = new ListNode(2);
		ListNode node5 = new ListNode(0);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		// ListNode temp = node1;
		ListNode temp = insertionSortList(node1);
		while (temp != null) {
			System.out.print(temp.val + ">");
			temp = temp.next;

		}

	}

	public static void insertSort(int a[]) {
		for (int i = 1; i < a.length; i++) {
			int rear = a[i];
			int j = i - 1;
			while (rear < a[j] && j > -1) {
				// 往后移动 ,且自减
				a[j + 1] = a[j];
				j--;
			}
			// 以最后一个数为基准，并0~n-1中比它小的数,交换位置
			a[j + 1] = rear;

		}
	}

	public static ListNode insertionSortList(ListNode head) {
		ListNode root = new ListNode(0); // 头结点
		root.next = head;
		ListNode p = head;
		ListNode q;
		ListNode r;

		while (p != null && p.next != null) {
			if (p.val <= p.next.val) {
				p = p.next;
			} else {
				q = p.next;
				p.next = q.next;

				r = root;
				// 找第一个大于等于q.val的前驱结点，因为在root.next到p之间必定存在这样的结点
				while (r.next.val <= q.val) {
					r = r.next;
				}
                //r = 1,3,5,0
				//q = 2,3,5,9
				q.next = r.next;
				r.next = q;
				//r = 0,1,2,3,5,0
			}
		}

		return root.next;
	}

}
